翻訳と辞書 Words near each other ・ Rectified truncated tetrahedron ・ Rectifier ・ Rectifier (disambiguation) ・ Rectifier (neural networks) ・ Rectiformer ・ Rectify ・ Rectilabrum ・ Rectilinear ・ Rectilinear lens ・ Rectilinear locomotion ・ Rectilinear minimum spanning tree ・ Rectilinear polygon ・ Rectilinear propagation ・ Rectilinear Research Corporation ・ Rectilinear scanner ・ Rectilinear Steiner tree ・ Rectina ・ Rectiostoma fernaldella ・ Rectiostoma xanthobasis ・ Rectipalpula ・ Rectipalpula billeti ・ Rectipilus ・ Rectiplanes ・ Rectiplanes delicatus ・ Rectisol ・ Recto and verso ・ Recto Avenue ・ Recto LRT Station ・ Recto tono ・ Recto Verso (album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Rectilinear Steiner tree ： ウィキペディア英語版 Rectilinear Steiner tree The rectilinear Steiner tree problem, minimum rectilinear Steiner tree problem (MRST), or rectilinear Steiner minimum tree problem (RSMT) is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance. The problem may be formally stated as follows: given ''n'' points in the plane, it is required to interconnect them all by a shortest network which consists only of vertical and horizontal line segments. It can be shown that such a network is a tree whose vertices are the input points plus some extra points (Steiner points).〔 The problem arises in the physical design of electronic design automation. In VLSI circuits, wire routing is carried out by wires running only in vertical and horizontal directions, due to high computational complexity of the task. Therefore wire length is the sum of the lengths of vertical and horizontal segments, and the distance between two pins of a net is actually the rectilinear distance ("Manhattan distance") between the corresponding geometric points in the design plane.〔Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"〕 ==Properties== It is known that the search for the RMST may be restricted to the Hanan grid, constructed by drawing vertical and horizontal lines through each vertex.〔M. Hanan, On Steiner’s problem with rectilinear distance, J. SIAM Appl. Math. 14 (1966), 255 - 265.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rectilinear Steiner tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.